package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * Description 桶排序
 *
 * @ClassName algorithm.sort.bucketSort
 * @Version 1.0
 * @Date: 2022/2/19 14:51
 * @Author xuyi
 */
public class BucketSort {
    private InsertSort insertSort = new InsertSort();

    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        bucketSort(arr,3);
    }

    /**
     * bucketNum 桶数量
     */
    private void bucketSort(int[] arr,int bucketNum){
        int[] maxAndMin = getMaxAndMin(arr);
        int min = maxAndMin[0],max = maxAndMin[1];
        //计算桶大小 bucketSize
        int bucketSize = (int)Math.floor((max-min)/bucketNum)+1;
        int[][] buckets = new int[bucketNum][0];
        //将每一个元素放入适当的桶中
        for (int i=0;i<arr.length;i++){
            int idx = (arr[i] - min)/bucketSize;
            buckets[idx] = arrAppend(buckets[idx],arr[i]);
        }
        int arrIdx = 0;
        for(int[] bucket:buckets){
            if(bucket.length<=0){
                continue;
            }
            insertSort.sort(bucket);
            for(int num:bucket){
                arr[arrIdx++] = num;
            }
        }
    }

    private int[] getMaxAndMin(int[] arr){
        int max = arr[0];
        int min = arr[0];
        for(int i =1;i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
            if(arr[i]<min){
                min=arr[i];
            }
        }
        return new int[]{min,max};
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}
